#ifndef ISOGRAPHEDITDISTANCE_HPP_INCLUDED
#define ISOGRAPHEDITDISTANCE_HPP_INCLUDED


#include <boost/lexical_cast.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/filtered_graph.hpp>
#include <boost/graph/graph_utility.hpp>
#include <boost/graph/iteration_macros.hpp>
#include <boost/graph/mcgregor_common_subgraphs.hpp>
#include <boost/property_map/shared_array_property_map.hpp>
#include <boost/foreach.hpp>


using namespace boost;

template <typename Graph>
struct subgraph_callback {


private:
    const Graph& m_graph1;

public:

    typedef typename graph_traits<Graph>::vertices_size_type VertexSizeFirst;

    subgraph_callback(const Graph& graph1, int& _tmp) :
    m_graph1(graph1), iMax(_tmp) {  }

    template <typename CorrespondenceMapFirstToSecond,
    typename CorrespondenceMapSecondToFirst>
    bool operator()(CorrespondenceMapFirstToSecond correspondence_map_1_to_2,
                  CorrespondenceMapSecondToFirst correspondence_map_2_to_1,
                  VertexSizeFirst subgraph_size) {

    iMax = subgraph_size;
    // Explore the entire space
    return (true);
  }

    int& iMax;
};


// A class for calculating graph edit distance with the subgraph isomorphic
// cost function as defined in "On a relation between graph edit distance and maximum common
// subgraph"(1997, Bunke).
// See also page 25 in "Classification and Clustering of
// Vector Space Embedded Graphs"
class IsoGraphEditDistance
{

public:
template <typename Graph>
    static double GraphEditDistance(Graph& G1, Graph& G2)
    {
        int iMax = 0;
        subgraph_callback<const Graph> user_callback(G1, iMax);

        typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
        typedef typename graph_traits<Graph>::edge_descriptor Edge;

        typedef typename property_map<Graph, vertex_name_t>::type VertexNameMap;
        typedef typename property_map<Graph, edge_name_t>::type EdgeNameMap;

        //VertexNameMap vname_map_simple1 = vertex_index_map(get(vertex_name, G1));
        //VertexNameMap vname_map_simple2 = vertex_index_map(get(vertex_name, G2));
        VertexNameMap vname_map_simple1 = get(vertex_name, G1);
        VertexNameMap vname_map_simple2 = get(vertex_name, G2);



        user_callback.iMax = 0;
        mcgregor_common_subgraphs_maximum
            (G1, G2, true, user_callback,
                vertices_equivalent(make_property_map_equivalent(vname_map_simple1, vname_map_simple2)));
        //cout << "iMax: " << iMax << " V(G1):"  << num_vertices(G1) << "V(G2):" << num_vertices(G2) << endl;
        //cout << iMax << endl;
        //return num_vertices(G1) + num_vertices(G2) - 2*user_callback.iMax;
        //return 1.0 - (double)(iMax)/(double)(max(num_vertices(G1), num_vertices(G2)));

       return 1.0 - (double)(iMax)/
        ( (double)num_vertices(G1) + (double)num_vertices(G2) - (double)(iMax) );
    }


template<typename Graph, template<typename T> class Container>
static Container<double> GetGraphCoordinate(const Container<const Graph>& gTraining,const Graph& kTarget )
{
    Container<double> kCoordinate;
    BOOST_FOREACH( const Graph*g, gTraining )
    {
        kCoordinate.push_back(GraphEditDistance(g, kTarget));
    }

    return kCoordinate;
}

};
#endif // ISOGRAPHEDITDISTANCE_HPP_INCLUDED
